package 每日一题;

import 我的JDK基础数据结构.HashMap.HashMap;

import java.util.List;
import java.util.Map;
import java.util.TreeMap;
import java.util.TreeSet;

public class No220存在重复元素III {

    /**
     * 给你一个整数数组 nums 和两个整数 k 和 t 。
     * 请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。
     * 如果存在则返回 true，不存在返回 false。
     *
     * 示例 1：
     * 输入：nums = [1,2,3,1], k = 3, t = 0
     * 输出：true
     * 示例 2：
     * 输入：nums = [1,0,1,1], k = 1, t = 2
     * 输出：true
     * 示例 3：
     * 输入：nums = [1,5,9,1,5,9], k = 2, t = 3
     * 输出：false
     *  
     * 提示：
     * 0 <= nums.length <= 2 * 104
     * -231 <= nums[i] <= 231 - 1
     * 0 <= k <= 104
     * 0 <= t <= 231 - 1
     */

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        //t->值差距  k->下标差距
        return method1(nums,k,t);
    }

    //最优解法: 桶排序
    public boolean method1(int[] nums,int k,int t) {
        if(nums.length<2){
            return false;
        }

        /**
         * 不知道有没有人疑惑，在比较id - 1和id + 1这两个相邻桶时，
         * 只比较了一个元素，这足够吗？哈希表的行为不是会用新元素覆盖旧元素，一个桶里有多个元素怎么办？
         * 其实是覆盖根本不会发生...因为一旦要覆盖，就说明存在两个元素同属一个桶，
         * 直接返回true了。这就是题解说的“一个桶内至多只会有一个元素”——数组输入里当然可以有多个元素属于同一个桶，
         * 但是一旦出现一对，算法就结束了。
         *
         * 所以我这里用TreeMap完全是没必要!
         */
        Map<Long, TreeMap<Integer,Integer>> map=new HashMap<>();

        int left=0;
        int right=0;

        while (right<nums.length){

            int num=nums[right];
            long bucketIndex = this.getBucketIndex(num, t);

            if(map.get(bucketIndex)!=null&&map.get(bucketIndex).size()!=0){
                TreeMap<Integer, Integer> treeMap = map.get(bucketIndex);
                if(treeMap.get(num)!=null){
                    return true;
                }
                Map.Entry<Integer, Integer> higherEntry = treeMap.higherEntry(num);
                Map.Entry<Integer, Integer> lowerEntry = treeMap.lowerEntry(num);
                if(higherEntry!=null&&Math.abs(higherEntry.getValue()-right)<=k&&Math.abs(((long)higherEntry.getKey()-(long)num))<=t){
                    return true;
                }
                if(lowerEntry!=null&&Math.abs(lowerEntry.getValue()-right)<=k&&Math.abs(((long)lowerEntry.getKey()-(long)num))<=t){
                    return true;
                }
            }
            if(map.get(bucketIndex-1)!=null&&map.get(bucketIndex-1).size()!=0){
                Integer maxNum = map.get(bucketIndex - 1).lastKey();
                Integer maxIndex = map.get(bucketIndex-1).get(maxNum);
                if(Math.abs(maxNum-nums[right])<=t&&Math.abs(maxIndex-right)<=k){
                    return true;
                }
            }
            if(map.get(bucketIndex+1)!=null&&map.get(bucketIndex+1).size()!=0){
                Integer minNum=map.get(bucketIndex+1).firstKey();
                Integer minIndex=map.get(bucketIndex+1).get(minNum);
                if(Math.abs(minNum-nums[right])<=t&&Math.abs(minIndex-right)<=k){
                    return true;
                }
            }
            if(map.get(bucketIndex)==null){
                TreeMap<Integer,Integer> treeMap=new TreeMap<>();
                treeMap.put(nums[right],right);
                map.put(bucketIndex,treeMap);
            }else{
                map.get(bucketIndex).put(nums[right],right);
            }
            right++;
            if(right-left>k){
                int removeNum=nums[left];
                bucketIndex=getBucketIndex(removeNum,t);
                map.get(bucketIndex).remove(removeNum);
                left++;
            }

        }

        return false;
    }

    private long getBucketIndex(int num,int t) {
        //怎么算桶呢? t=3
        // -5 [-4 -3 -2 -1] [0 1 2 3] [4 5 6 7] 8
        // 桶要比对当前和相邻的,无需强制完美一个桶
        return (long)num/((long)(t+1));
    }

    public static void main(String[] args) {
        No220存在重复元素III n=new No220存在重复元素III();
        int[] arr={2147483647,-1,2147483647};
        boolean result = n.containsNearbyAlmostDuplicate(arr, 1, 2147483647);
        System.out.println(result);
    }

}
